/*
 * sparc-specific code analysis
 * $Id: sparc_analyze.c,v 1.13 2012/07/21 00:05:04 curt Exp $
 *
 * XXX- this stuff leaks memory like a collander
 * we handle all the delayed branch stuff here -
 * if conditional branch and annulled, we build a little branch-let containing the delayed instruction.
 * if  not annulled,
 */

/*
 * idiomatic sparc stuff:
 *
 * function called never returns, but returns to *our* caller:
 *     load o7 into a temp,
 *     call foo,
 *     and load the temp back into o7 in the delay slot
 * used for bar() { ... ; return foo(); }
 *
 */

#include "decomp.h"
#include "sparc.h"

/* condition encodings and names */
char *cond_bcc[] = {
    "never", "equal", "less or equal", "less",
    "less or equal unsigned", "less unsigned", "negative", "overflow",
    "always", "not equal", "greater", "greater or equal",
    "greater unsigned", "greater or equal unsigned",
    "positive", "not overflow"
};

char *cond_movr[] = {
    "", "equal zero", "non-positive", "negative",
    "", "not zero", "positive", "non-negative"
};

char *cond_movcc[] = {
    /* float */
    "never", "not equal", "less or greater", "unordered or less",
    "less", "unordered or greater", "greater", "unordered",
    "always", "equal", "unordered or equal", "greater or equal",
    "unordered or greater or equal", "less or equal",
    "unordered or less or equal", "ordered",
    /* integer */
    "never", "equal", "less or equal", "less",
    "less or equal unsigned", "less unsigned", "negative", "overflow",
    "always", "not equal", "greater", "greater or equal",
    "greater unsigned", "greater or equal unsigned",
    "positive", "not overflow",

};
char *cond_fbfcc[] = {
    "never", "not equal", "less or greater", "unordered or less",
    "less", "unordered or greater", "greater", "unordered",
    "always", "equal", "unordered or equal", "greater or equal",
    "unordered or greater or equal", "less or equal", "unordered or less or equal", "ordered"
};

struct condtype conditions[] = {
    { SC_BCC, &cond_bcc, { 0, 0 } },
    { SC_MOVR, &cond_movr, { 0 } },
    { SC_MOVCC, &cond_movcc, { 0 } },
    { SC_FMOVCC, &cond_movcc, { 0 } },
    { SC_FMOVR, &cond_movr, { 0 } },
    { SC_FBFCC, &cond_fbfcc, { 0 } },
    { SC_FBPFCC, &cond_fbfcc, { 0 } },
};


char *regname[] = {
    "g0", "g1", "g2", "g3", "g4", "g5", "g6", "g7",
    "o0", "o1", "o2", "o3", "o4", "o5", "o6", "o7",
    "l0", "l1", "l2", "l3", "l4", "l5", "l6", "l7",
    "i0", "i1", "i2", "i3", "i4", "i5", "i6", "i7",
};

void
expr_init()
{
    static int inited = 0;
    int i;

    if (!inited) {
        g0_expr = make_expr(O_CONST, 0, 0, 0, 0);
        ret_expr = make_expr(O_RETADDR, 0, 0, 0, 0);
        sp_expr = make_expr(O_STACK, 0, 0, 0, 0);

        c10_expr = make_expr(O_CONST, 0, 0, 0, 10);
        c32_expr = make_expr(O_CONST, 0, 0, 0, 32);
        c42_expr = make_expr(O_CONST, 0, 0, 0, 42);

        m22_expr = make_expr(O_CONST, 0, 0, 0, 0x3fffff);
        m10_expr = make_expr(O_CONST, 0, 0, 0, 0x3ff);

        for (i = 0; i < 32; i++) {
            reg_expr[i] = make_expr(O_REG, 0, 0, 0, i);
        }
        reg_expr[REG_G0] = g0_expr;
        reg_expr[REG_O7] = ret_expr;
        reg_expr[REG_O6] = sp_expr;

        inited = 1;
    }
}

/*
 * create a new register file
 */
regfile *
make_regfile()
{
    int i;
    regfile *rf;

    rf = malloc(sizeof *rf);
    for (i = 0; i < MAXREGS; i++) {
        rf->reg[i] = 0;
    }

    rf->reg[REG_G0] = g0_expr;
    rf->reg[REG_O7] = ret_expr;
    rf->reg[REG_O6] = sp_expr;
    rf->saved = 0;
}

/* copy a register file */
regfile *
clone_regs(regfile *srf)
{
    regfile *crf;
    int i;

    crf = malloc(sizeof(*crf));
    for (i = 0; i < MAXREGS; i++) {
        crf->reg[i] = srf->reg[i];
    }
    crf->saved = srf->saved;
    return crf;
}

/* dump out a register file scoreboard */
void
dumpregs(regfile *rf)
{
    int b, r;

    printf("\nregs 0x%x saved 0x%x", (unsigned int)rf, (unsigned int)rf->saved);
    printf("\nb   0  1  2  3  4  5  6  7");
    for (b = 0; b < 4; b++) {
        printf("\n%c: ", "goli"[b]);
        for (r = 0; r < 8; r++) {
            if (rf->reg[b*8+r])
                printf(" * ");
            else
                printf("   ");
        }
    }
    printf("\n");
}

/*
 * adjust register window for save
 * this means, copy out to in, clear local and out
 */
regfile *
push_regs(regfile *rf)
{
    regfile *nrf;
    int i;

    nrf = clone_regs(rf);
    nrf->saved = rf;
    for (i = 0; i < 8; i++) {
        nrf->reg[REG_I0+i] = rf->reg[REG_O0+i];
        nrf->reg[REG_L0+i] = 0;
        nrf->reg[REG_O0+i] = 0;
    }
    return nrf;
}

/* adjust register window for restore */
regfile *
pop_regs(regfile *rf)
{
    regfile *nrf;
    int i;

    nrf = rf->saved;
    for (i = 0; i < 8; i++) {
        nrf->reg[REG_G0+i] = rf->reg[REG_G0+i];
        nrf->reg[REG_O0+i] = rf->reg[REG_I0+i];
    }
    return nrf;
}

/*
 * given an expression tree, see if we can calculate the value
 * of the tree further, applying any constant value operators
 * we structure this as a number of potential folds.
 */

int
expr_eq(expr *e1, expr *e2) {
    if (e1 == e2) return 1;
    if (e1->op != e2->op) return 0;
    if (e1->op == O_CONST && e1->val == e2->val) return 1;
    if (e1->op == O_SYMBOL && e1->symbol == e2->symbol) return 1;
    if (!expr_eq(e1->left, e2->left)) return 0;
    if (!expr_eq(e1->right, e2->right)) return 0;
    return 1;
}

int disable_fold = 0x0;

/*
 * this important case is of a right shift followed by a left shift.
 * the hair comes from an intervening AND operation
 * ((expr >> const1) & constmask) << const2  =
 *	(expr >> (const1 - const2)) & constmask >> (const1 - const2)
 */
int
fold1(expr **epp)
{
    expr *ep = *epp;
    int diff;
    expr *ne;
    expr *me;
    expr *se;

    if (disable_fold & 1) return (0);

    if (ep->op == O_LSHIFT &&
            ep->right->op == O_CONST &&
            ep->left->op == O_AND &&
            ep->left->right->op == O_CONST &&
            ep->left->left->op == O_RSHIFT &&
            ep->left->left->right->op == O_CONST) {

        diff = ep->left->left->right->val - ep->right->val;

        if (diff >= 0) {

            me = make_expr(O_CONST, 0, 0, 0,
                ep->left->right->val << ep->right->val);
            ne = ep->left->left->left;
            if (diff > 0) {
                se = make_expr(O_CONST, 0, 0, 0, diff);
                ne = make_expr(O_RSHIFT, ne, se, 0, 0);
            }
            *epp = make_expr(O_AND, ne, me, 0, 0);
            return (1);
        }
    }
    return (0);
}

/*
 * this case is an OR of 2 ands of the same thing
 * with non-overlapping masks
 */
int
fold2(expr **epp)
{
    expr *ep = *epp;

    if (disable_fold & 2) return (0);

    /* XXX - check masks */
    if (ep->op == O_OR &&
            ep->left->op == O_AND &&
            ep->right->op == O_AND &&
            expr_eq(ep->left->left, ep->right->left) &&
            ep->left->right->op == O_CONST &&
            ep->right->right->op == O_CONST) {

            *epp = make_expr(O_AND, ep->left->left,
                    make_expr(O_CONST, 0, 0, 0,
                        ep->left->right->val |
                        ep->right->right->val), 0, 0);

            return (1);
    }
    return 0;
}

/*
 * this case is an ADD of 2 ands of the same thing
 * with non-overlapping masks
 */
int
fold3(expr **epp)
{
    expr *ep = *epp;

    if (disable_fold & 4) return (0);

    /* XXX - check masks */
    if (ep->op == O_ADD &&
            ep->left->op == O_AND &&
            ep->right->op == O_AND &&
            expr_eq(ep->left->left, ep->right->left) &&
            ep->left->right->op == O_CONST &&
            ep->right->right->op == O_CONST) {

            *epp = make_expr(O_AND, ep->left->left,
                    make_expr(O_CONST, 0, 0, 0,
                        ep->left->right->val +
                        ep->right->right->val), 0, 0);

            return (1);
    }
    return (0);
}

/*
 * boolean no-ops
 */
int
fold4(expr **epp)
{
    expr *ep = *epp;

    if (disable_fold & 8) return (0);

    if ((ep->op == O_AND && ep->right->op == O_CONST &&
            ep->right->val == 0xffffffffffffffff) ||
        (ep->op == O_OR && ep->right->op == O_CONST && ep->right->val == 0)) {
        *epp = ep->left;
        return (1);
    }
    if ((ep->op == O_AND && ep->left->op == O_CONST &&
            ep->left->val == 0xffffffffffffffff) ||
        (ep->op == O_OR && ep->left->op == O_CONST && ep->left->val == 0)) {
        *epp = ep->right;
        return (1);
    }
    return (0);
}

/*
 * these are straightforward constant expressions
 */
int
fold5(expr **epp)
{
    expr *ep = *epp;

    if (disable_fold & 0x10) return (0);

    switch (ep->op) {

    case O_LSHIFT:
        if ((ep->right->op == O_CONST) && (ep->left->op == O_CONST)) {
            ep->left->val <<= ep->right->val;
            *epp = ep->left;
            return (1);
        }
        break;

    case O_ADD:
        if ((ep->right->op == O_CONST) && (ep->left->op == O_CONST)) {
            ep->left->val += ep->right->val;
            *epp = ep->left;
            return (1);
        }
        break;

    default:
        break;
    }
    return (0);
}

/*
 * keep folding until no more folds possible
 */
expr *
fold(expr *ep)
{
    int passes = 0;

    if (verbose & VERBOSE_FOLD) {
        dump_expr(ep, 1, "pre-fold");
    }

    while (fold1(&ep) ||
           fold2(&ep) ||
           fold3(&ep) ||
           fold4(&ep) ||
           fold5(&ep)) {

        passes++;
    }

    if (verbose & VERBOSE_FOLD) {
        if (passes) {
            dump_expr(ep, 1, "post-fold");
        } else {
            printf("\nno change\n");
        }
    }
    return (ep);
}

/*
 * turn a data reference, which may contain compile-time arithmetic
 * on a symbol, into an expression tree.
 * this would be way prettier in lisp.
 */
expr *
ref_expr(reference *rp)
{
    expr *ep;
    expr *sep;

    sep = make_expr(O_SYMBOL, 0, 0, rp->place, 0);

    switch (rp->howcode) {
    case RELOC_LL10:
        ep = make_expr(O_AND, sep, m10_expr, 0, 0);
        break;
    case RELOC_HH22:
        sep = make_expr(O_RSHIFT, sep, c42_expr, 0, 0);
        ep = make_expr(O_AND, sep, m22_expr, 0, 0);
        break;
    case RELOC_HM10:
        sep = make_expr(O_RSHIFT, sep, c32_expr, 0, 0);
        ep = make_expr(O_AND, sep, m10_expr, 0, 0);
        break;
    case RELOC_LM22:
	case RELOC_HI22:
        sep = make_expr(O_RSHIFT, sep, c10_expr, 0, 0);
        ep = make_expr(O_AND, sep, m22_expr, 0, 0);
        break;
    default:
        printf("ref expr %d %x\n", rp->howcode, rp->howcode);
        break;
    }
    return ep;
}

/*
 * left hand side computation - store address
 */
expr *
sinister_expr(inst *ip)
{
    expr *ep = 0;
    itype *itp;
    int rs1, rs2;
    regfile *rf;

    itp = &instr[ip->type];
    rs1 = ip->attr[A_RS1];
    rs2 = ip->attr[A_RS2];
    rf = ip->state;

    ASSERT((itp->syndrome & S_STORE));
    /*
     * a store instruction is really an add of 2 operands,
     * and then the store. we need to generate these expression trees
     * so that we can run the combiner to get useful address
     * expressions
     */
    if (itp->syndrome & S_RS2) {
        /* interesting special case of adds with G0 */
        if (rs1 == REG_G0) {
            ep = rf->reg[rs2];
        } else if (rs2 == REG_G0) {
            ep = rf->reg[rs1];
        } else {
            ep = make_expr(O_ADD, rf->reg[rs1], rf->reg[rs2], 0, 0);
        }
    } else {
        /* we reference a symbol */
        if (ip->ref[0]) {
            ep = make_expr(O_ADD, rf->reg[rs1],
			   ref_expr(ip->ref[0]), 0, 0);
        } else {
            ep = make_expr(O_CONST, 0, 0, 0, ip->attr[A_DISP]);
            /* XXX - lose - WTF - tiny constant address */
        }
    }
    return ep;
}

/*
 * walk an expression tree, resolving it according to the contents
 * of the register file
 */
expr *
resolve_expr(expr *ep, regfile *rf)
{
    switch (ep->op) {

    case O_REG:
        if (rf->reg[ep->val]) {
            ep = rf->reg[ep->val];
        }
        break;

    case O_LOAD: case O_NOT: case O_NEG:
        ep->left = resolve_expr(ep->left, rf);
        break;

    case O_OR: case O_AND: case O_XOR:
    case O_ADD: case O_SUB: case O_MUL: case O_DIV:
    case O_LSHIFT: case O_RSHIFT:
    case O_LAND: case O_LOR: case O_LNOT:
        ep->left = resolve_expr(ep->left, rf);
        ep->right = resolve_expr(ep->right, rf);

    default:
        break;
    }

    ep = fold(ep);
    return (ep);
}

#ifdef notdef
/*
 * check if our operand is a function argument, if so, reference it.
 */
expr *
arg_test(int regnum, expr *ep) {
    if (ep) {
        return (ep);
    }
    if (regnum >= REG_I0 && regnum <= REG_I7) {
        ep = arg_expr[regnum - REG_I0];
    } else {
        printf("arg_test: null expression in register %d\n", regnum);
        ep = arg_expr[0];
    }
    return (ep);
}
#endif

/*
 * analyze instruction data issues
 */
void
analyze_inst(inst *ip, inst *pip)
{
    itype *itp;
    inst *dip;
    label *lp;
    reference *rp;
    expr *ep;


    itp = &instr[ip->type];

    if (pip) {
        ip->state = clone_regs(pip->state);
    } else {
        ip->state = make_regfile();
    }

#ifdef notdef
    /* this involves a tweak of the register window */
    if (itp->syndrome & S_SAVE) {
        expr *de = dest_expr(ip);
        lastregs = ip->state = push_regs(lastregs);
        if (ip->attr[A_RD] != REG_G0) {
            ip->state->reg[ip->attr[A_RD]] = de;
        }
    }

    /* this involves a different tweak of the register window */
    if (itp->syndrome & S_RESTORE) {
        expr *de = dest_expr(ip);
        lastregs = ip->state = pop_regs(lastregs);
        if (ip->attr[A_RD] != REG_G0) {
            ip->state->reg[ip->attr[A_RD]] = de;
        }
    }

    if (itp->syndrome & S_LOAD) {
        ip->state->reg[ip->attr[A_RD]] =
            make_expr(O_LOAD, dest_expr(ip), 0, 0, 0);
    }



    if (itp->syndrome & S_STORE) {
        function *fp;
        code *cp;
        fp = funcs;

        ip->attr[A_WIDTH] = store_width[(opcode >> 19) & 0xf];
        cp = make_code(C_STORE);
        cp->arg1 = sinister_expr(ip);
        cp->arg2 = ip->state->reg[ip->attr[A_RD]];
    }
#endif
    /*
     * this requires us to kill the out registers,
     * and deal with the delay slot.
     */
    if (itp->syndrome & S_CALL) {
    }

    if ((itp->syndrome & S_RD) && (ip->attr[A_RD] != 0) &&
        !(itp->syndrome & (S_LOAD | S_STORE | S_SAVE | S_RESTORE))) {
        ep = resolve_expr(ip->calc, ip->state);
        ip->state->reg[ip->attr[A_RD]] = ep;
    }

    if (itp->syndrome & S_LOAD) {
        ep = resolve_expr(ip->calc, ip->state);
        ep = make_expr(O_LOAD, ep, 0, 0, 0);
        if (ip->attr[A_RD] != REG_G0) {
            ip->state->reg[ip->attr[A_RD]] = ep;
        }
    }
}

/*
 * given a function, which is a header to a bunch of instructions,
 * generate register lifetime stuff.
 */
void
analyze_function(function *fp)
{
    inst *ip;
    label *lp;
    int i;
    inst *pip;  /* previous instr */

    /*
     * we need to do some delayed branch stuff:
     * instructions in the delay slot of calls are inserted before the call.
     * non-anulled conditional branch delay slots too.
     * annulled conditional, hmmm.. XXX maybe replicated at the destination
     */
    printf("\nanalyze_function: %s\n", fp->label->name);
    pip = 0;
    for (ip = fp->tree; ip; ip = ip->next) {

        switch (imax) {
        default:
            imax--;
        case -1:
            break;
        case 0:
            return;
        }

        lp = lookup_label(fp->sect, ip->offset);
        if (verbose & VERBOSE_FLOW) {
            if (lp) {
                printf("%s: (refs %d)\n", lp->name, ip->refcnt);
            }
        }
        for (i = 0; i < ip->refcnt; i++) {
            if (ip->flow[i]->offset != ip->offset - 4) {
                if (verbose & VERBOSE_FLOW) {
                    printf("\tfrom %x\n", ip->flow[i]->offset);
                }
            }
        }
        if (instr[ip->type].syndrome & S_IF) {
            if (verbose & VERBOSE_FLOW) {
                printf("\n");
            }
        }
        analyze_inst(ip, pip);
        if (verbose & VERBOSE_INST) {
            dump_inst(ip);
        }
        pip = ip;
    }
}


